package org.laizili.solution.codinginterviews;

import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.*;

import org.laizili.structure.list.Node;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/4ueAj6/">剑指 Offer II 029. 排序的循环链表</a>
 * <p>
 * tags: (循环)链表
 * <p>
 * 注意：<a href="https://leetcode-cn.com/problems/insert-into-a-sorted-circular-linked-list/">本题与主站 708 题相同</a>
 */
public class Problem029 {


    private static class Solution {
        // 向非严格递增的循环链表中插入结点，使得插入后的链表仍然保持有序
        public Node insert(Node head, int insertVal) {
            // 空链表
            if (head == null) {
                Node node = new Node(insertVal);
                node.next = node;
                return node;
            }
            // 只有一个结点
            if (head.next == head) {
                head.next = new Node(insertVal, head.next);
                return head;
            }

            // find real head
            Node prev = head;      // real tail: 最大值
            Node cur = head.next; // real head: 最小值
            while (prev.val <= cur.val && cur != head) {
                prev = cur;
                cur = cur.next;
            }
            if (insertVal <= cur.val || insertVal >= prev.val) {
                prev.next = new Node(insertVal, prev.next);
            } else {
                Node lastPos = null;
                Node insertedPos = cur;
                while (insertedPos.val < insertVal) {
                    lastPos = insertedPos;
                    insertedPos = insertedPos.next;
                }
                lastPos.next = new Node(insertVal, insertedPos);
            }
            return head;
        }
    }

    private Solution solution;

    @Before
    public void init() {
        solution = new Solution();
    }


    @Test
    public void testcase_1() {
        // test case 1
        Node node1 = new Node(1);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        // 构造循环链表
        node1.next = node3;
        node3.next = node4;
        node4.next = node1;
        // 使得 node3 成为head
        Node head = node3;
        solution.insert(head, 2);
        var res = toList(head);
        assertEquals(List.of(3, 4, 1, 2), res);

    }

    @Test
    public void testcase_2() {
        // 空链表
        Node head = solution.insert(null, 11);
        var res = toList(head);
        assertEquals(List.of(11), res);
        // 只有一个结点
        Node node = new Node(1);
        node.next = node;
        solution.insert(node, 0);
        res = toList(node);
        assertEquals(List.of(1, 0), res);
    }

    @Test
    public void testcase_3() {
        Node node1 = new Node(1);
        Node node2 = new Node(5, node1);
        node1.next = node2;
        Node head = solution.insert(node1, 5);
        var res = toList(head);
        assertEquals(List.of(1, 5, 5), res);
    }

    // 获取结点值列表
    private static List<Integer> toList(Node head) {
        List<Integer> vals = new ArrayList<>();
        if (head != null) {
            vals.add(head.val);
            Node cur = head.next;
            while (cur != head) {
                vals.add(cur.val);
                cur = cur.next;
            }
        }
        return vals;
    }
}
